{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Consecutive Sequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #union-find #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #并查集 #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestConsecutive"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长连续序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个未排序的整数数组 <code>nums</code> ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。</p>\n",
    "\n",
    "<p>请你设计并实现时间复杂度为 <code>O(n)</code><em> </em>的算法解决此问题。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [100,4,200,1,3,2]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>最长数字连续序列是 <code>[1, 2, 3, 4]。它的长度为 4。</code></pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [0,3,7,2,5,8,4,6,0,1]\n",
    "<strong>输出：</strong>9\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 <= nums.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup> <= nums[i] <= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-consecutive-sequence](https://leetcode.cn/problems/longest-consecutive-sequence/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-consecutive-sequence](https://leetcode.cn/problems/longest-consecutive-sequence/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[100,4,200,1,3,2]', '[0,3,7,2,5,8,4,6,0,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        s_nums = sorted(set(nums))\n",
    "        diff = []\n",
    "        for i in range(len(s_nums) - 1):\n",
    "            # print(s_nums[i])\n",
    "            # print(s_nums[i + 1])\n",
    "            diff.append(s_nums[i+1] - s_nums[i])\n",
    "        counter = 0\n",
    "        tmp = 0\n",
    "        for j in diff:\n",
    "            if j == 1:\n",
    "                tmp += 1\n",
    "                if tmp > counter:\n",
    "                    counter = tmp\n",
    "            # elif j == 0:\n",
    "            #     pass\n",
    "            else:\n",
    "                tmp =0\n",
    "        return counter + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype:  int\n",
    "        \"\"\"\n",
    "        temp = nums\n",
    "        res = 0\n",
    "        while temp:\n",
    "            x= temp.pop(0)\n",
    "            left= x - 1\n",
    "            right = x + 1\n",
    "            res1 = 1\n",
    "            while left in temp:\n",
    "                temp.remove(left)\n",
    "                left -=1\n",
    "                res1 +=1\n",
    "            while right in temp:\n",
    "                temp.remove(right)\n",
    "                right +=1\n",
    "                res1 +=1\n",
    "            res = max(res,res1)\n",
    "        \n",
    "        return res\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        snums = sorted(nums)\n",
    "        dp = [1 for _ in nums]\n",
    "        for i in range(1,len(snums)):\n",
    "            if snums[i] == snums[i-1]+1:\n",
    "                dp[i] = dp[i-1] + 1\n",
    "            elif snums[i] == snums[i-1]:\n",
    "                dp[i] = dp[i-1]\n",
    "            else:\n",
    "                pass\n",
    "        if len(nums)==0:\n",
    "            return 0\n",
    "        else:\n",
    "            return max(dp)  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        s = set(nums)\n",
    "        n = len(nums)\n",
    "        maxcount = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] - 1 in s:\n",
    "                continue\n",
    "            num = nums[i]\n",
    "            count = 0\n",
    "            while num in s:\n",
    "                count += 1\n",
    "                num += 1\n",
    "            maxcount = max(maxcount, count)\n",
    "        return maxcount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        #许多个集合，若x-1在A集合中，x+1在B集合中，则A+B+{x}\n",
    "        #初始化并查树\n",
    "        if nums==[]:\n",
    "            return 0\n",
    "        re=1\n",
    "        set1=set(nums)\n",
    "        while set1:\n",
    "            y=1\n",
    "            x=set1.pop()\n",
    "            a,b=x,x\n",
    "            while a+1 in set1:\n",
    "                y+=1\n",
    "                set1.remove(a+1)\n",
    "                a+=1\n",
    "            while b-1 in set1:\n",
    "                y+=1\n",
    "                set1.remove(b-1)\n",
    "                b-=1\n",
    "            if y>re:\n",
    "                re=y\n",
    "        return re\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if nums == []:\n",
    "            return 0\n",
    "        \n",
    "        n = set(nums)\n",
    "        count = 1\n",
    "        longest = 1\n",
    "        \n",
    "        for i in n:\n",
    "            right = i\n",
    "            if i-1 not in n:\n",
    "                right = i+1\n",
    "                while right in n:\n",
    "                    right += 1\n",
    "            longest = max(longest, right-i)\n",
    "            print(i, longest)\n",
    "                \n",
    "        return longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(nums) < 2:\n",
    "            return len(nums)\n",
    "        LC = []\n",
    "        for item in set(nums):\n",
    "            #head small\n",
    "            idxHead, idxTail = -1,-1\n",
    "            i=0\n",
    "            while i<len(LC):\n",
    "                if len(LC[i]) == 0:  i+=1;  continue\n",
    "                if idxHead == -1 and item+1 in LC[i]: \n",
    "                    idxHead = i\n",
    "                    LC[i].add(item)\n",
    "                if idxTail == -1 and item-1 in LC[i]:  \n",
    "                    idxTail = i\n",
    "                    LC[i].add(item)\n",
    "                i+=1\n",
    "            if idxHead + idxTail == -2:\n",
    "                #not find\n",
    "                s = set()\n",
    "                s.add(item)\n",
    "                LC.append(s)\n",
    "            elif idxHead >= 0 and idxTail >= 0:\n",
    "                LC[idxTail] = LC[idxTail] | LC[idxHead]\n",
    "                LC[idxHead] = set()\n",
    "        return max([len(sq) for sq in LC])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def longestConsecutive(self, nums):\n",
    "        maxlength = 0   # 最大连续子序列的长度\n",
    "\n",
    "        # 为每个连续子序列向后添加元素\n",
    "        ascMap = {}    # key:上升连续序列最后一个数字   value:上升连续序列\n",
    "        descMap = {}  # key:上升连续序列第一个数字   value:上升连续序列\n",
    "        for num in nums:\n",
    "            if num not in ascMap.keys() and num not in descMap.keys():\n",
    "                if num-1 in ascMap.keys():  # 该数字是某个连续子序列的下个元素\n",
    "                    cons = ascMap.pop(num-1)\n",
    "                    cons.append(num)\n",
    "                    ascMap[num] = cons\n",
    "                    descMap[cons[0]] = cons\n",
    "                else:   # 该数字当前不与任何数字构成连续序列\n",
    "                    ascMap[num] = [num]\n",
    "                    descMap[num] = [num]\n",
    "\n",
    "        # 为每个连续子序列向前添加元素\n",
    "        keys = list(ascMap.keys())[:]\n",
    "        for key in keys:\n",
    "            if key in ascMap.keys():\n",
    "                while ascMap[key][0] - 1 in ascMap.keys():\n",
    "                    pre = ascMap.pop(ascMap[key][0] - 1)[:]\n",
    "                    ascMap[key] = pre + ascMap[key]\n",
    "                print(ascMap[key])\n",
    "                if len(ascMap[key]) > maxlength:\n",
    "                    maxlength = len(ascMap[key])\n",
    "\n",
    "        return maxlength"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # if len(nums) == 0:\n",
    "        #     return 0\n",
    "        # nums.sort()\n",
    "        # res = 0\n",
    "        # l = 1\n",
    "        # for i in range(1, len(nums)):\n",
    "        #     if nums[i] - nums[i - 1] == 1:\n",
    "        #         l += 1\n",
    "        #     elif nums[i] == nums[i - 1]:\n",
    "        #         continue\n",
    "        #     else:\n",
    "        #         res = max(l, res)\n",
    "        #         l = 1\n",
    "        # return max(l, res)\n",
    "        map = {}\n",
    "        for i in set(nums):\n",
    "            map[i] = 1\n",
    "        x = 1\n",
    "        res = 0\n",
    "        for i in set(nums):\n",
    "            if map.__contains__(i):\n",
    "                map.pop(i)\n",
    "                b = i\n",
    "                while map.__contains__(i - 1):\n",
    "                    x += 1\n",
    "                    map.pop(i - 1)\n",
    "                    i -= 1\n",
    "                while map.__contains__(b + 1):\n",
    "                    x += 1\n",
    "                    map.pop(b + 1)\n",
    "                    b += 1\n",
    "            res = max(res, x)\n",
    "            x = 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # 方法二：并查集\n",
    "        # 本题实际上就是求无向图的最大连通分量\n",
    "        # 根据昨天学习的算法导论上的并查集，我需要写一个并查集，方法包括：makeset, union, findset\n",
    "        # 我发现可以使用hashmap和hashset实现上述三个方法\n",
    "        if not nums:\n",
    "            return 0\n",
    "        hashset = set(nums)\n",
    "        ans = 1\n",
    "        rep = {} # representative -> set\n",
    "        find = {} # number -> representative, O(1)\n",
    "        # makeset, O(n)\n",
    "        for number in hashset:\n",
    "            find[number] = number\n",
    "            rep[number] = {number}\n",
    "        # findset and union\n",
    "        for number in hashset:\n",
    "            a = number\n",
    "            for b in [a-1, a+1]:\n",
    "                if b in hashset:\n",
    "                    ra, rb = find[a], find[b]\n",
    "                    if ra != rb:\n",
    "                        s1, s2 = len(rep[ra]), len(rep[rb])\n",
    "                        if s1 > s2:\n",
    "                            ra, rb = rb, ra\n",
    "                        rep[rb] |= rep[ra]\n",
    "                        ans = max(ans, len(rep[rb]))\n",
    "                        for i in rep[ra]:\n",
    "                            find[i] = rb\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        dic={}\n",
    "        if nums==[]:\n",
    "            return 0\n",
    "        maxrst=0\n",
    "        for num in nums:\n",
    "           \n",
    "            if dic.get(str(num),0)!=0:\n",
    "                continue\n",
    "            L=dic.get(str(num-1),0)\n",
    "            R=dic.get(str(num+1),0)\n",
    "            dic[str(num)]=1+L+R\n",
    "            dic[str(num+R)]=1+L+R\n",
    "            dic[str(num-L)]=1+L+R\n",
    "            maxrst=max(maxrst,1+L+R)\n",
    "            #print(dic)\n",
    "        return maxrst\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        maxlength = 0\n",
    "        while nums:\n",
    "            count = 1\n",
    "            a = nums[0] + 1\n",
    "            b = nums[0] - 1\n",
    "            while 1:\n",
    "                if a in nums:\n",
    "                    count += 1\n",
    "                    nums.remove(a)\n",
    "                    a += 1\n",
    "                else:\n",
    "                    break\n",
    "            while 1:\n",
    "                if b in nums:\n",
    "                    count += 1\n",
    "                    nums.remove(b)\n",
    "                    b -= 1\n",
    "                else:\n",
    "                    break\n",
    "            nums.remove(nums[0])\n",
    "            maxlength = max(maxlength, count)\n",
    "        return maxlength"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        cur_max = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] == nums[i-1]:\n",
    "                continue          \n",
    "            if nums[i] == nums[i-1] + 1:\n",
    "                cur_max += 1\n",
    "                res = max(res, cur_max)\n",
    "            else:\n",
    "                cur_max = 1\n",
    "        return max(res, cur_max)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        if len(nums)==1:\n",
    "            return 1\n",
    "        if len(nums)==0:\n",
    "            return 0\n",
    "        start=nums[0]\n",
    "        maxlian=1\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]-nums[i-1]>1:\n",
    "                start=nums[i]\n",
    "            maxlian=max(maxlian,nums[i]-start+1)\n",
    "        return maxlian\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        nums_set = set(nums)\n",
    "        n = len(nums_set)\n",
    "        max_all = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]-1 in nums_set:\n",
    "                continue\n",
    "            else:\n",
    "                max_ = 1\n",
    "                for j in range(1,n+1):\n",
    "                    if nums[i]+j in nums_set: max_ +=1\n",
    "                    else: break \n",
    "                max_all = max(max_all,max_)\n",
    "        return max_all\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        d={}\n",
    "\n",
    "        for x in nums:\n",
    "            if x not in d:\n",
    "                left=d.get(x-1,0)\n",
    "                right=d.get(x+1,0)\n",
    "                tmp=left+right+1\n",
    "\n",
    "                d[x]=tmp \n",
    "                d[x-left]=tmp \n",
    "                d[x+right]=tmp \n",
    "                ans=max(ans,tmp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        res = 1\n",
    "        tem =1\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i] == nums[i-1]:\n",
    "                continue\n",
    "            if nums[i]-1 == nums[i-1]:\n",
    "                res+=1\n",
    "                tem = max(tem,res)\n",
    "            else:\n",
    "                res = 1\n",
    "        return tem \n",
    "\n",
    "      \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if not nums: return 0\n",
    "        cur_num = 1\n",
    "        nums.sort()\n",
    "        max_length = 1\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i] == nums[i-1]:\n",
    "                continue\n",
    "            elif nums[i] -1 == nums[i-1]:\n",
    "                cur_num += 1\n",
    "                max_length = max(max_length, cur_num)\n",
    "            else:\n",
    "                cur_num = 1\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\r\n",
    "        result = {}\r\n",
    "        max = 0\r\n",
    "        for i in nums:\r\n",
    "            if i not in result:\r\n",
    "                result[i] = [i,i]\r\n",
    "                temp_min = i\r\n",
    "                temp_max = i\r\n",
    "                if i-1 in result:\r\n",
    "                    temp_min = result[i-1][0]\r\n",
    "                if i+1 in result:\r\n",
    "                    temp_max = result[i+1][1]\r\n",
    "                result[temp_max] = result[temp_min] = [temp_min,temp_max]\r\n",
    "                if temp_max-temp_min+1 > max:\r\n",
    "                    max = temp_max-temp_min+1\r\n",
    "        #max = 0\r\n",
    "        #for i in result:\r\n",
    "        #    if result[i][1]-result[i][0]+1 > max:\r\n",
    "        #        max = result[i][1]-result[i][0]+1\r\n",
    "        return max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        \n",
    "        nums = list(set(nums))\n",
    "        father_dict = {n: n for n in nums}\n",
    "        length_dict = {n: 1 for n in nums}\n",
    "        depth_dict = {n: 0 for n in nums}\n",
    "\n",
    "        def find_father(n):\n",
    "            father = father_dict[n]\n",
    "            if father_dict[father] != father:\n",
    "                father_dict[n] = find_father(father)\n",
    "            return father_dict[n]\n",
    "\n",
    "        def merge(n1, n2):\n",
    "            father1 = find_father(n1)\n",
    "            father2 = find_father(n2)\n",
    "\n",
    "            if father1 != father2:\n",
    "                rank1 = depth_dict[father1]\n",
    "                rank2 = depth_dict[father2]\n",
    "\n",
    "                if rank1 < rank2:\n",
    "                    father_dict[father1] = father2\n",
    "                    length_dict[father2] += length_dict[father1]\n",
    "                else:\n",
    "                    father_dict[father2] = father1\n",
    "                    length_dict[father1] += length_dict[father2]\n",
    "                if rank1 == rank2:\n",
    "                    depth_dict[father1] += 1\n",
    "\n",
    "        for n in nums:\n",
    "            if n - 1 in father_dict:\n",
    "                merge(n, n - 1)\n",
    "            if n + 1 in father_dict:\n",
    "                merge(n, n + 1)\n",
    "\n",
    "        return max(length_dict.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class node:\n",
    "    def __init__(self):\n",
    "        self.after = None \n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        heads = []\n",
    "        dic = {}\n",
    "        for i in nums:\n",
    "            dic[i] = node()\n",
    "\n",
    "        for i in nums:\n",
    "            if i+1 in nums:\n",
    "                dic[i].after = dic[i+1]\n",
    "            if i-1 not in nums:\n",
    "                heads.append(i)\n",
    "        \n",
    "        res = 0\n",
    "\n",
    "        for i in heads:\n",
    "            head = dic[i]\n",
    "            count = 0\n",
    "            while head:\n",
    "                head = head.after\n",
    "                count += 1\n",
    "            res = max(res,count)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        node = dict()\n",
    "        rank = dict()\n",
    "\n",
    "        def make_set(point):#初始化，每个节点的父节点是自己\n",
    "            node[point] = point\n",
    "            rank[point] = 1\n",
    "            \n",
    "        def find(point):#找代表节点\n",
    "            if node[point] != point:\n",
    "                node[point] = find(node[point])#压缩\n",
    "            return node[point]\n",
    "\n",
    "        def merge(point1, point2):#节点所在集合融合\n",
    "            root1 = find(point1)\n",
    "            root2 = find(point2)\n",
    "            if root1 != root2:\n",
    "                if rank[root1] > rank[root2]:\n",
    "                    node[root2] = root1\n",
    "                    rank[root1]=rank[root2]+rank[root1]\n",
    "                else:\n",
    "                    node[root1] = root2\n",
    "                    rank[root2] += rank[root1]\n",
    "                return \n",
    "            else:\n",
    "                return \n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            make_set(i)\n",
    "        num_dict=dict()\n",
    "        for i,num in enumerate(nums):\n",
    "            if num  in num_dict:\n",
    "                continue\n",
    "            else:\n",
    "                num_dict[num]=i\n",
    "            if num+1 in num_dict:\n",
    "                merge(num_dict[num+1],i)\n",
    "            if num-1 in num_dict:\n",
    "                merge(num_dict[num-1],i)\n",
    "        \n",
    "        graphs=defaultdict(list)\n",
    "        for i in range(len(nums)):\n",
    "            graphs[find(i)].append(i)\n",
    "        return len(max(graphs.items(),key=lambda t:len(t[1]))[1]) \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 排序\n",
    "# class Solution:\n",
    "#     def longestConsecutive(self, nums: List[int]) -> int:\n",
    "#         ans = 0\n",
    "#         nums = sorted(set(nums))\n",
    "#         n = len(nums)\n",
    "#         l,r = 0,-1\n",
    "#         for i in range(n):\n",
    "#             if nums[i]-nums[i-1]==1 or i==0:\n",
    "#                 r += 1\n",
    "#             else:\n",
    "#                 l = r = i\n",
    "#             ans = max(ans,r-l+1)\n",
    "#         return ans\n",
    "\n",
    "# 哈希表\n",
    "# class Solution:\n",
    "#     def longestConsecutive(self, nums: List[int]) -> int:\n",
    "#         ans = 0\n",
    "#         d = {}\n",
    "#         for num in nums:\n",
    "#             if (num,0) in d:\n",
    "#                 continue\n",
    "#             d[num,1] = d[num+1,1] if (num+1,1) in d else num\n",
    "#             d[num,0] = d[num-1,0] if (num-1,0) in d else num\n",
    "#             d[d[num,0],1] = d[num,1]\n",
    "#             d[d[num,1],0] = d[num,0]\n",
    "#             ans = max(ans,d[num,1]-d[num,0]+1)\n",
    "#         return ans\n",
    "\n",
    "# 哈希表\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        d = defaultdict(int)\n",
    "        for num in set(nums):\n",
    "            d[num,1] = d[num+1,1]+1\n",
    "            d[num,0] = d[num-1,0]+1\n",
    "            d[num-d[num,0]+1,1] = d[num,0]+d[num,1]-1\n",
    "            d[num+d[num,1]-1,0] = d[num,0]+d[num,1]-1\n",
    "            ans = max(ans,d[num,0]+d[num,1]-1)\n",
    "        return ans\n",
    "\n",
    "# class Solution:\n",
    "#     def longestConsecutive(self, nums):\n",
    "#         longest_streak = 0\n",
    "#         num_set = set(nums)\n",
    "\n",
    "#         for num in num_set:\n",
    "#             if num - 1 not in num_set:\n",
    "#                 current_num = num\n",
    "#                 current_streak = 1\n",
    "\n",
    "#                 while current_num + 1 in num_set:\n",
    "#                     current_num += 1\n",
    "#                     current_streak += 1\n",
    "\n",
    "#                 longest_streak = max(longest_streak, current_streak)\n",
    "\n",
    "#         return longest_streak"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums) -> int:\n",
    "        max_val = 0\n",
    "        cnt = len(nums)\n",
    "        arr = self.__get_map_arr(cnt)\n",
    "        for ii in nums:\n",
    "            idx = ii % cnt\n",
    "            val = {'pre': None, 'post': None}\n",
    "            arr[idx][ii] = val\n",
    "            idx = (ii - 1) % cnt\n",
    "            if (ii - 1) in arr[idx]:\n",
    "                tmp_val = arr[idx][ii - 1]\n",
    "                val['pre'] = tmp_val\n",
    "                tmp_val['post'] = val\n",
    "            idx = (ii + 1) % cnt\n",
    "            if (ii + 1) in arr[idx]:\n",
    "                tmp_val = arr[idx][ii + 1]\n",
    "                val['post'] = tmp_val\n",
    "                tmp_val['pre'] = val\n",
    "        for ii in arr:\n",
    "            for jj in ii.keys():\n",
    "                tmp_val = 0\n",
    "                pre = ii[jj]\n",
    "                while pre is not None:\n",
    "                    tmp_val += 1\n",
    "                    pre = pre['pre']\n",
    "                if tmp_val > max_val:\n",
    "                    max_val = tmp_val\n",
    "        print(max_val)\n",
    "        return max_val\n",
    "\n",
    "    def __get_map_arr(self, cnt):\n",
    "        arr = []\n",
    "        for i in range(0, cnt):\n",
    "            arr.append({})\n",
    "        return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, nums):\n",
    "        self.parent = dict()\n",
    "        self.rank = dict()\n",
    "        self.maxRank = 0\n",
    "        for num in nums:\n",
    "            self.parent[num] = num\n",
    "            self.rank[num] = 1\n",
    "            self.maxRank = max(self.maxRank, self.rank[num])\n",
    "        self.nums = list(self.parent.keys())\n",
    "        self.n = len(self.nums)\n",
    "        \n",
    "    \n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        px, py = self.find(x), self.find(y)\n",
    "        # x and y already connected\n",
    "        if px == py:\n",
    "            return False\n",
    "        # make sure px <= py\n",
    "        if px > py:\n",
    "            px, py = py, px\n",
    "        self.parent[px] = py\n",
    "        self.rank[py] += self.rank[px]\n",
    "        self.maxRank = max(self.maxRank, self.rank[py])\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        # Time: O(n)\n",
    "        # Space: O(n)\n",
    "        uf = UnionFind(nums)\n",
    "        for num in uf.nums:\n",
    "            if num - 1 in uf.parent:\n",
    "                uf.union(num - 1, num)\n",
    "            if num + 1 in uf.parent:\n",
    "                uf.union(num, num + 1)\n",
    "        return uf.maxRank\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.root = list(range(n))\n",
    "        self.count = [1 for _ in range(n)]\n",
    "        # print(self.root)\n",
    "        # print(self.count)\n",
    "\n",
    "    def find_root(self, val):\n",
    "        if self.root[val] == val:\n",
    "            return self.root[val]\n",
    "        self.root[val] = self.find_root(self.root[val])\n",
    "        return self.root[val]\n",
    "\n",
    "    def merge(self, x, y):\n",
    "        root_x = self.find_root(x)\n",
    "        root_y = self.find_root(y)\n",
    "        if root_x != root_y:\n",
    "            self.count[root_x] += self.count[root_y]\n",
    "            self.count[root_y] = 0\n",
    "            self.root[root_y] = root_x\n",
    "\n",
    "    def isconn(self, x, y):\n",
    "        return self.find_root(x) == self.find_root(y)\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        UF = UnionFind(len(nums))\n",
    "        nums_dic = {}\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] in nums_dic:\n",
    "                continue\n",
    "            nums_dic[nums[i]] = i\n",
    "            \n",
    "            if nums[i] + 1 in nums_dic:\n",
    "                UF.merge(i, nums_dic[nums[i] + 1])\n",
    "            if nums[i] - 1 in nums_dic:\n",
    "                UF.merge(i, nums_dic[nums[i] - 1])\n",
    "            # print(nums_dic)\n",
    "            # print('root:',UF.root)\n",
    "            # print('count:',UF.count)\n",
    "            # print('\\n')\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(len(UF.root)):\n",
    "            if i == UF.root[i]:\n",
    "                ans = max(ans, UF.count[i])\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        import heapq\n",
    "        heapq.heapify(nums)\n",
    "        i,ans,n=1,1,len(nums)\n",
    "        if n==0 or n==1:\n",
    "            return n\n",
    "        \n",
    "        start = heapq.heappop(nums)\n",
    "        for _ in range(1,n):\n",
    "            nex = heapq.heappop(nums)\n",
    "            if start+1==nex :\n",
    "                i+=1\n",
    "                start+=1\n",
    "            elif start==nex:\n",
    "                continue\n",
    "            else:\n",
    "                i=1\n",
    "                start = nex\n",
    "            ans=max(ans,i)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        ans = 1\n",
    "        temp = 1\n",
    "        pre = nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] == pre + 1:\n",
    "                temp += 1\n",
    "                ans = max(ans, temp)\n",
    "                pre = nums[i]\n",
    "            elif nums[i] != pre:\n",
    "                pre = nums[i]\n",
    "                temp = 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        import heapq\n",
    "        chan = len(nums)\n",
    "        if chan == 0:\n",
    "            return 0\n",
    "        if chan == 1:\n",
    "            return 1\n",
    "        ans = 1\n",
    "        heapq.heapify(nums)\n",
    "        shang = nums[0]\n",
    "        lin = 1\n",
    "        while nums:\n",
    "            if nums[0] == shang:\n",
    "                heapq.heappop(nums)\n",
    "                continue\n",
    "            if nums[0] == shang + 1:\n",
    "                lin += 1\n",
    "                shang = nums[0]\n",
    "                heapq.heappop(nums)\n",
    "            else:\n",
    "                if lin > ans:\n",
    "                    ans = lin\n",
    "                lin = 1\n",
    "                shang = nums[0]\n",
    "                heapq.heappop(nums)\n",
    "        if not nums:\n",
    "            if lin > ans:\n",
    "                ans = lin\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        # 这个数组没有排序  找出连续的序列 这个序列不要求在原数组中连续\n",
    "\n",
    "        if not nums:\n",
    "            return 0\n",
    "\n",
    "\n",
    "        # 排序的做法\n",
    "        nums = sorted(nums)\n",
    "        l,r=0,1\n",
    "        max_len=1\n",
    "        print(nums)\n",
    "        count=1\n",
    "        while r<len(nums):\n",
    "            if nums[r]-nums[r-1]==1:\n",
    "                count+=1\n",
    "                max_len=max(max_len,count)\n",
    "                r+=1\n",
    "            elif nums[r]-nums[r-1]==0:\n",
    "                r+=1\n",
    "                continue\n",
    "            else:\n",
    "                count=1\n",
    "                l=r\n",
    "                r+=1\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        heapq.heapify(nums)\n",
    "        cur = 1\n",
    "        res = 1\n",
    "        x1  = heapq.heappop(nums)\n",
    "        while nums:\n",
    "            x2 = heapq.heappop(nums)\n",
    "            while nums and x1 == x2:\n",
    "                x2 = heapq.heappop(nums)\n",
    "            if x2 - x1 == 1:\n",
    "                cur += 1\n",
    "            else:\n",
    "                res = max(res, cur)\n",
    "                cur = 1\n",
    "            x1 = x2\n",
    "        return max(res, cur)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        if not nums:return 0\n",
    "        dp=[1]*len(nums)\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]-nums[i-1]==1:\n",
    "                dp[i]=dp[i-1]+1\n",
    "            elif nums[i]==nums[i-1]:\n",
    "                dp[i]=dp[i-1]\n",
    "\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        dp = [1 for i in range(len(nums))]   ###最短的递增子序列长度为1\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i] - nums[i-1] ==1:\n",
    "                dp[i] = dp[i-1]+1\n",
    "            if nums[i] == nums[i-1]:\n",
    "                dp[i] = dp[i-1]\n",
    "        return max(dp)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if len(nums ) == 0:\n",
    "            return 0\n",
    "        nums = sorted(nums)\n",
    "        dp = [1] * len(nums)\n",
    "        maxL = 1\n",
    "        count = 0\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i] - nums[i-1] == 1:\n",
    "                dp[i] = 1+ dp[i-1]\n",
    "                maxL = max(maxL, dp[i])\n",
    "            elif nums[i] == nums[i-1]:\n",
    "                dp[i] = dp[i-1]\n",
    "                count +=1\n",
    "        return maxL\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 1.0\n",
    "# class Solution:\n",
    "#     def longestConsecutive(self, nums: List[int]) -> int:\n",
    "#         if not nums:\n",
    "#             return 0\n",
    "#         nums.sort()\n",
    "#         maxl = 0\n",
    "#         fast = 1\n",
    "#         slow = 0\n",
    "\n",
    "#         while fast < len(nums):\n",
    "#             if nums[fast] - nums[fast - 1] == 1:\n",
    "#                 fast += 1\n",
    "#             elif nums[fast] == nums[fast - 1]:\n",
    "#                 fast += 1\n",
    "#                 slow += 1\n",
    "#             else:\n",
    "#                 maxl = max(maxl, fast - slow)\n",
    "#                 slow = fast\n",
    "#                 fast += 1\n",
    "\n",
    "#         return max(maxl, fast - slow)\n",
    "\n",
    "# 2.0\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        maxl = 0\n",
    "        fast = 1\n",
    "        slow = 0\n",
    "\n",
    "        while fast < len(nums):\n",
    "            if nums[fast] == nums[fast - 1]:\n",
    "                slow += 1\n",
    "            elif nums[fast] - nums[fast - 1] > 1:\n",
    "                maxl = max(maxl, fast - slow)\n",
    "                slow = fast\n",
    "            fast += 1\n",
    "\n",
    "        return max(maxl, fast - slow)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        stack=[nums[0]]\n",
    "        ans=1\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]==stack[-1]:\n",
    "                continue\n",
    "            if nums[i]==stack[-1]+1:\n",
    "                stack.append(nums[i])\n",
    "            else:\n",
    "                ans=max(ans,len(stack))\n",
    "                stack=[nums[i]]\n",
    "        if stack:\n",
    "            ans=max(ans,len(stack))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        import heapq\n",
    "        heapq.heapify(nums)\n",
    "        result = 0\n",
    "        sub_s = None\n",
    "        sub_l = 0\n",
    "        while len(nums)>0:\n",
    "            num = heapq.heappop(nums)\n",
    "            if sub_s==None:\n",
    "                sub_s = num\n",
    "                sub_l += 1\n",
    "            else:\n",
    "                if num==sub_s+1:\n",
    "                    sub_l += 1\n",
    "                    sub_s = num\n",
    "                elif num==sub_s:\n",
    "                    continue\n",
    "                else:\n",
    "                    result = max(result, sub_l)\n",
    "                    sub_l = 1\n",
    "                    sub_s = num\n",
    "        result = max(result, sub_l)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        dp = [1 for i in range(len(nums))]\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] - nums[i-1] ==1:\n",
    "                dp[i] = dp[i-1]+1\n",
    "            elif nums[i] == nums[i-1]:\n",
    "                dp[i] = dp[i-1]\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if nums == []:\n",
    "            return 0\n",
    "        else:\n",
    "            heapify(nums)  # 将列表转为堆对象\n",
    "            count = tmpcount = 1\n",
    "            prev = heappop(nums)\n",
    "            while nums:\n",
    "                curr = heappop(nums)\n",
    "                if curr == prev:\n",
    "                    continue\n",
    "                elif curr == prev + 1:\n",
    "                    tmpcount += 1\n",
    "                else:\n",
    "                    count = max(count, tmpcount)\n",
    "                    tmpcount = 1\n",
    "                prev = curr\n",
    "            count = max(count, tmpcount)\n",
    "            return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        import heapq\n",
    "\n",
    "        if not nums:\n",
    "            return 0\n",
    "\n",
    "        heapq.heapify(nums)\n",
    "\n",
    "        ans = 1\n",
    "        result = 1\n",
    "\n",
    "        element = heapq.heappop(nums)\n",
    "        while nums:\n",
    "            check = heapq.heappop(nums)\n",
    "            if check == element + 1:\n",
    "                element = check\n",
    "                result += 1\n",
    "                ans = max(result, ans)\n",
    "            elif check == element:\n",
    "                continue\n",
    "            else:\n",
    "                element = check\n",
    "                result = 1\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        nums = sorted(nums)\n",
    "        count = 1 if nums else 0\n",
    "        print(nums)\n",
    "        k = 1\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[i] + 1 == nums[i+1]:\n",
    "                k += 1\n",
    "                count = max(count, k)\n",
    "            elif nums[i] == nums[i+1]:\n",
    "                pass\n",
    "            else:\n",
    "                k = 1\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if len(nums)>0:\n",
    "            nums = sorted(nums)\n",
    "            res = 1\n",
    "            m = res\n",
    "            print(nums)\n",
    "            for i in range(1, len(nums)):\n",
    "                if nums[i]-nums[i-1]==1 or nums[i]-nums[i-1]==0 :\n",
    "                    if nums[i]-nums[i-1]!=0:\n",
    "                        res+=1\n",
    "                else:\n",
    "                    m = max(res, m)\n",
    "                    res = 1\n",
    "            m = max(res, m)\n",
    "            return m\n",
    "        else:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        from collections import Counter\n",
    "        cnt = Counter()\n",
    "        max_cnt = 0\n",
    "        i = 0\n",
    "        while i < len(nums):\n",
    "            if i > 0 and nums[i] == nums[i-1]:\n",
    "                nums.pop(i)\n",
    "            else:\n",
    "                diff = nums[i] - i\n",
    "                cnt[diff] += 1\n",
    "                if max_cnt < cnt[diff]:\n",
    "                    max_cnt = cnt[diff]\n",
    "                i += 1\n",
    "        return max_cnt\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        nums = sorted(nums)\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        dp = [1] * len(nums)\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] - nums[i-1] == 1:\n",
    "                dp[i] += dp[i-1]\n",
    "            elif nums[i] == nums[i-1]:\n",
    "                dp[i] = dp[i-1]\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        if l == 0:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        start, end = 0, 0\n",
    "        res = 1\n",
    "        for i in range(1, l):\n",
    "            if nums[i-1] == nums[i] - 1:\n",
    "                end += 1\n",
    "            elif nums[i-1] == nums[i]:\n",
    "                start += 1\n",
    "                end += 1\n",
    "            else:\n",
    "                start = end = i \n",
    "            res = max(res, end-start+1)\n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n < 2:\n",
    "                return n\n",
    "        tmp,maxLen = 1,1\n",
    "        # 排序\n",
    "        nums = sorted(nums)\n",
    "        for i in range(1, n):\n",
    "            # 跳过重复元素\n",
    "            if nums[i]==nums[i-1]: continue\n",
    "            # 若递增，tmp+1\n",
    "            elif nums[i]-nums[i-1] ==1:\n",
    "                tmp+= 1\n",
    "            # 递增结束，刷新最大记录\n",
    "            else:\n",
    "                maxLen = max(maxLen, tmp)\n",
    "                tmp=1\n",
    "        # 再次刷新记录，以处理递增到数组结束的情况\n",
    "        return max(maxLen, tmp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        count = 1 \n",
    "        ans = 1\n",
    "\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] == nums[i-1] + 1:\n",
    "                count += 1\n",
    "                ans = max(ans, count)\n",
    "            #elif 语句中添加对相邻元素是否相等的判断，以避免重复计算。\n",
    "            elif nums[i] != nums[i-1]:\n",
    "                count = 1\n",
    "        return ans\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "\n",
    "        # if not nums:\n",
    "        #     return 0\n",
    "        # nums.sort()\n",
    "        # count = 1\n",
    "        # ans = 1\n",
    "        # for i in range(len(nums)-1):\n",
    "        #     if nums[i]+1 == nums[i+1]:\n",
    "        #         count +=1\n",
    "        #         ans = max(ans,count)\n",
    "        #     else:\n",
    "        #         count = 1\n",
    "        # return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        # solution 1: sort, but not O(n)\n",
    "        nums.sort()\n",
    "        hash_list = collections.defaultdict(int)\n",
    "        for num in nums:\n",
    "            if num - 1 in hash_list:\n",
    "                hash_list[num] = hash_list[num - 1] + 1\n",
    "                hash_list.pop(num - 1)\n",
    "            elif num not in hash_list:\n",
    "                hash_list[num] = 1\n",
    "        if not hash_list:\n",
    "            return 0\n",
    "        return max(hash_list.values())\n",
    "\n",
    "        # solution 2: dp\n",
    "        # hash_list = collections.defaultdict(int)\n",
    "        # max_len = 0\n",
    "        # for num in nums:\n",
    "        #     if num not in hash_list:\n",
    "        #     # get current length: left_len + right_len + 1 and updata max_len\n",
    "        #         left_len = hash_list.get(num - 1, 0)\n",
    "        #         right_len = hash_list.get(num + 1, 0)\n",
    "        #         cur_len = left_len + right_len + 1\n",
    "        #         max_len = max(max_len, cur_len)\n",
    "\n",
    "        #         # update hash table:\n",
    "        #         hash_list[num - left_len] = cur_len\n",
    "        #         hash_list[num + right_len] = cur_len\n",
    "        #         hash_list[num] = cur_len\n",
    "            \n",
    "        # return max_len\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        hash_table = {}\n",
    "        for n in sorted(nums):\n",
    "            if n in hash_table.keys():\n",
    "                continue\n",
    "            if n - 1 in hash_table.keys():\n",
    "                hash_table[n - 1] += 1\n",
    "                hash_table[n] = hash_table.pop(n - 1)\n",
    "            else:\n",
    "                hash_table[n] = 1\n",
    "        return max(hash_table.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        dict = collections.defaultdict(int)\n",
    "        # nums.sort()\n",
    "        sorted_nums = sorted(nums)\n",
    "        for num_i in sorted_nums:\n",
    "            if num_i - 1 in dict:\n",
    "                dict[num_i] = dict[num_i-1] + 1\n",
    "                dict.pop(num_i - 1)\n",
    "            elif num_i not in dict:\n",
    "                dict[num_i] = 1\n",
    "        return max(dict.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        num_set = set(nums)\n",
    "        for num in nums:\n",
    "            if num - 1 not in num_set:\n",
    "                count = 1\n",
    "                while num+1 in num_set:\n",
    "                    count += 1\n",
    "                    num += 1\n",
    "                res = max(res, count) \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        s = sorted(set(nums))\n",
    "        startsub = 0\n",
    "        coti = 0\n",
    "        nextsub = 1\n",
    "        for n in s:\n",
    "            if nextsub < len(s):\n",
    "                if n +1 != s[nextsub]:\n",
    "                    coti = max(nextsub-startsub, coti)\n",
    "                    startsub = nextsub\n",
    "                nextsub += 1\n",
    "            else:\n",
    "                coti = max(nextsub - startsub, coti)\n",
    "        return coti"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        _nums = list(set(nums.copy()))\n",
    "        _nums.sort()\n",
    "        cur, max_res = 1, 1\n",
    "        _nums_len = len(_nums)\n",
    "        if _nums_len in [0, 1]:\n",
    "            return _nums_len\n",
    "        for idx in range(0, _nums_len - 1):\n",
    "            if _nums[idx+1] == _nums[idx] + 1:\n",
    "                cur += 1\n",
    "                max_res = cur if cur > max_res else max_res\n",
    "            else:\n",
    "                cur = 1\n",
    "        return max_res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        res = 0     # 记录最长连续序列的长度\n",
    "        num_set = set(nums)     # 记录nums中的所有数值\n",
    "        print(num_set)\n",
    "        for num in num_set:\n",
    "            # 如果当前的数是一个连续序列的起点，统计这个连续序列的长度\n",
    "            if (num - 1) not in num_set:\n",
    "                seq_len = 1     # 连续序列的长度，初始为1\n",
    "                while (num + 1) in num_set:\n",
    "                    seq_len += 1\n",
    "                    num += 1    # 不断查找连续序列，直到num的下一个数不存在于数组中\n",
    "                res = max(res, seq_len)     # 更新最长连续序列长度\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        nums = list(set(nums))\n",
    "        nums.sort()\n",
    "        res = {}   \n",
    "        n = len(nums)\n",
    "        print(nums)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        else:\n",
    "            j = 0\n",
    "            res[j] = 1\n",
    "            for i in range(1,n):\n",
    "                if nums[i-1] + 1 == nums[i]:\n",
    "                    res[j] += 1\n",
    "                else:\n",
    "                    j += 1\n",
    "                    res[j] = 1\n",
    "            return max(res.values())\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        mp = collections.defaultdict(int)\n",
    "        num_set = set(nums)\n",
    "        for num in nums:\n",
    "            if num - 1 not in num_set:\n",
    "                count = 1\n",
    "                a = num\n",
    "                while num+1 in num_set:\n",
    "                    count += 1\n",
    "                    num += 1\n",
    "                mp[a] = count \n",
    "        return max(list(mp.values())) if nums != [] else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        hash_dict = {}\n",
    "        nums_set = set(nums)\n",
    "        for num in nums_set:\n",
    "            if num - 1 not in nums_set:\n",
    "                hash_dict[num] = 1\n",
    "                i = 1\n",
    "                while num + i in nums_set:\n",
    "                    hash_dict[num] += 1\n",
    "                    i += 1\n",
    "            else:\n",
    "                continue\n",
    "        return max(hash_dict.values()) if hash_dict != {} else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        hashdict = collections.defaultdict(int)\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            if num not in hashdict:\n",
    "                left = hashdict.get(num - 1, 0)\n",
    "                right = hashdict.get(num + 1, 0)\n",
    "                hashdict[num] = left + 1 + right\n",
    "                res = max(res, hashdict[num])\n",
    "\n",
    "                hashdict[num-left] = hashdict[num]\n",
    "                hashdict[num+right] = hashdict[num]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        '''\n",
    "        nums.sort()\n",
    "        C = []\n",
    "        count = 1\n",
    "        if len(nums) <= 1:\n",
    "            return len(nums)\n",
    "        i=0\n",
    "        while i <= len(nums) - 2:\n",
    "            if nums[i + 1] - nums[i] == 1:\n",
    "                count += 1\n",
    "                C.append(count)\n",
    "\n",
    "            if nums[i + 1] - nums[i] == 0:\n",
    "                count += 0\n",
    "                C.append(count)\n",
    "\n",
    "            if nums[i + 1] - nums[i] != 1 and nums[i + 1] - nums[i] != 0:\n",
    "                C.append(count)\n",
    "                count=1\n",
    "            i+=1\n",
    "        return max(C)\n",
    "        '''\n",
    "        hash_dict = dict()\n",
    "        \n",
    "        max_length = 0\n",
    "        for num in nums:\n",
    "            if num not in hash_dict:\n",
    "                left = hash_dict.get(num - 1, 0)\n",
    "                right = hash_dict.get(num + 1, 0)\n",
    "                \n",
    "                cur_length = 1 + left + right\n",
    "                if cur_length > max_length:\n",
    "                    max_length = cur_length\n",
    "                \n",
    "                hash_dict[num] = cur_length\n",
    "                hash_dict[num - left] = cur_length\n",
    "                hash_dict[num + right] = cur_length\n",
    "                \n",
    "        return max_length\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        sort_list = sorted(nums)\n",
    "        map = {}\n",
    "        for item in sort_list:\n",
    "            if item-1 in map.keys():\n",
    "                map[item] = map[item-1] + 1\n",
    "            else:\n",
    "                map[item] = 1\n",
    "        return max(map.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        max_len = 0\n",
    "\n",
    "        s = set(nums)\n",
    "        ad = set()\n",
    "        for num in s:\n",
    "            if num in ad:\n",
    "                continue\n",
    "            cur_len = 0 \n",
    "            while num in s:\n",
    "                ad.add(num)\n",
    "                cur_len += 1\n",
    "                num += 1\n",
    "            max_len = max(max_len, cur_len)\n",
    "        return max_len\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "\n",
    "        left = {}\n",
    "        right = {}\n",
    "        visited = set()\n",
    "\n",
    "        for n in nums:\n",
    "            if n in visited:\n",
    "                continue\n",
    "            else:\n",
    "                visited.add(n)\n",
    "            if n+1 not in left and n-1 not in right:\n",
    "                left[n] = n\n",
    "                right[n] = n\n",
    "            elif n+1 in left and n-1 not in right:\n",
    "                cur_left = n+1\n",
    "                cur_right = left[cur_left]\n",
    "                left.pop(cur_left)\n",
    "                left[n] = cur_right\n",
    "                right[cur_right] = n\n",
    "            elif n+1 not in left and n-1 in right:\n",
    "                cur_right = n-1\n",
    "                cur_left = right[cur_right]\n",
    "                right.pop(cur_right)\n",
    "                right[n] = cur_left\n",
    "                left[cur_left] = n\n",
    "            elif n+1 in left and n-1 in right:\n",
    "                new_left = right[n-1]\n",
    "                new_right = left[n+1]\n",
    "\n",
    "                left.pop(n+1)\n",
    "                right.pop(n-1)\n",
    "\n",
    "                left[new_left] = new_right\n",
    "                right[new_right] = new_left\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        # nums.sort()\n",
    "        # print(nums)\n",
    "        # print(left)\n",
    "        # print(right)\n",
    "\n",
    "        for l in left:\n",
    "            r = left[l]\n",
    "            ans = max(ans, r - l + 1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        # 用not可以判断list是否为空\n",
    "        if not nums:\n",
    "            return 0;\n",
    "        # 用len()函数可以获取list的长度\n",
    "        n = len(nums)\n",
    "        mp = collections.defaultdict(list)\n",
    "        for num in nums:\n",
    "            mp[num] = 1\n",
    "        ans = 1\n",
    "        for num in nums:\n",
    "            if mp[num + 1] != 1:\n",
    "                now = 0\n",
    "                while mp[num]:\n",
    "                    now += 1\n",
    "                    num -= 1\n",
    "                ans = max(ans, now)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if len(nums)==0:\n",
    "            return 0\n",
    "        dicts = {}\n",
    "        max_length = 0\n",
    "        for i in nums:\n",
    "            if i + 1 not in dicts.keys():\n",
    "                dicts[i+1] = 0\n",
    "            if i - 1 not in dicts.keys():\n",
    "                dicts[i-1] = 0\n",
    "            if i not in dicts.keys() or dicts[i] == 0:\n",
    "                dicts[i] = dicts[i-1] + dicts[i+1] + 1\n",
    "                dicts[i-dicts[i-1]] = dicts[i]\n",
    "                dicts[i+dicts[i+1]] = dicts[i]\n",
    "                max_length = max(max_length, dicts[i])\n",
    "                dicts[i]\n",
    "                \n",
    "        return max_length\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        if len(nums)==0:\n",
    "            return 0\n",
    "        dicts = {}\n",
    "        max_length = 0\n",
    "        for i in nums:\n",
    "            if i + 1 not in dicts.keys():\n",
    "                dicts[i+1] = 0\n",
    "            if i - 1 not in dicts.keys():\n",
    "                dicts[i-1] = 0\n",
    "            if i not in dicts.keys() or dicts[i] == 0:\n",
    "                dicts[i] = dicts[i-1] + dicts[i+1] + 1\n",
    "                dicts[i-dicts[i-1]] = dicts[i]\n",
    "                dicts[i+dicts[i+1]] = dicts[i]\n",
    "                max_length = max(max_length, dicts[i])\n",
    "                dicts[i]\n",
    "                \n",
    "        return max_length\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        dict={}\n",
    "        nums=sorted(nums)\n",
    "        if nums == []:\n",
    "            return 0\n",
    "        for i in nums:\n",
    "            if i not in dict:\n",
    "                #dict[i]=1\n",
    "                dict[i+1]=1\n",
    "            else:\n",
    "                dict[i+1]=dict[i]+1\n",
    "        return (max(dict.values()))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
